package model;

/**
 * 
 * @author BENAMMAR Riyadh
 */
public class LCS_branch_and_bound {

	static int bounbsByLevel[];
	static String sequence1;
	static String sequence2;
   /**
 * This method compute the longuest common subsequence between x and y. It uses the 
 * Branch and Bound version of the recursive algorithm. For the first method call the third 
 * parameter must be equal to 0
 * @param x the first sequence
 * @param y the second sequence
 * @param distanceToRoot the number of explored parent nodes (search tree level) 
 * @return The longuest common subsequence
 */

	public static String lcs(String x, String y, int distanceToRoot) {
		int minLength = Math.min(x.length(), y.length());
		// System.out.println("x: " + x + " y: " + y + " distance= " +
		// distanceToRoot);
		if (y.equalsIgnoreCase(""))
			return "";
		if (minLength + distanceToRoot <= bounbsByLevel[distanceToRoot]) {
			// System.out.println("undevelopped node");
			return "";
		}
		/*
		 * int maxLength=Math.max(x.length(), y.length()); String
		 * x1=x.length()==minLength?x:y; String y1=x.length()==maxLength?x:y;
		 * if(minLength==maxLength){ x1=x; y1=y; }
		 */
		String commonSubsequence;

		char c = x.charAt(x.length() - 1);

		if (y.contains("" + c)) {
			if (x.length() == 1) {
				return "" + c;
			}
			commonSubsequence = lcs(x.substring(0, x.length() - 1),
					y.substring(0, y.lastIndexOf(c)), distanceToRoot + 1)
					+ c;
			bounbsByLevel[distanceToRoot] = commonSubsequence.length();
			// System.out.println("common sequence:" +
			// commonSubsequence+" at level: "+distanceToRoot);
			if (commonSubsequence.length() > bounbsByLevel[distanceToRoot])
				bounbsByLevel[distanceToRoot] = commonSubsequence.length();
			return commonSubsequence;
		} else {
			if (x.length() == 1 || y.length() == 1) {
				return "";
			}
			String subSequence1 = lcs(x.substring(0, x.length() - 1), y,
					distanceToRoot + 1);
			String subSequence2 = lcs(x, y.substring(0, y.length() - 1),
					distanceToRoot);
			commonSubsequence = subSequence1.length() > subSequence2.length() ? subSequence1
					: subSequence2;
			// System.out.println("common sequence:" +
			// commonSubsequence+" at level: "+distanceToRoot);
			if (commonSubsequence.length() > bounbsByLevel[distanceToRoot])
				bounbsByLevel[distanceToRoot] = commonSubsequence.length();
			return commonSubsequence;
		}
	}

	public static String lcs(String a, String b) {

		String[] sO = Tools.OrderStrings(a, b);
		sequence1 = sO[0];
		sequence2 = sO[1];

		int max = Math.max(a.length(), b.length());
		bounbsByLevel = new int[max + 1];
		for (int i = 0; i <= max; i++) {
			bounbsByLevel[i] = 0;
		}

		String r = lcs(sequence1, sequence2, 0);
		// System.out.println("lcs:\t: " + r + " et est de longueur " +
		// r.length());
		return r;
	}
}